<!DOCTYPE html>
<html lang="zh-CN">
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="robots" content="noodp" />
        <title>lab1-实现StreamReassembler - L_B__</title><meta name="referrer" content="no-referrer">
<meta name="description" content="lab1-实现StreamReassembler"><meta property="og:title" content="lab1-实现StreamReassembler" />
<meta property="og:description" content="lab1-实现StreamReassembler" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://acking-you.github.io/posts/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/" /><meta property="og:image" content="https://acking-you.github.io/logo.png"/><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2023-04-13T00:00:00+00:00" />
<meta property="article:modified_time" content="2023-04-13T00:00:00+00:00" />

<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://acking-you.github.io/logo.png"/>

<meta name="twitter:title" content="lab1-实现StreamReassembler"/>
<meta name="twitter:description" content="lab1-实现StreamReassembler"/>
<meta name="application-name" content="FeelIt">
<meta name="apple-mobile-web-app-title" content="FeelIt"><meta name="theme-color" content="#ffffff"><meta name="msapplication-TileColor" content="#da532c"><link rel="canonical" href="https://acking-you.github.io/posts/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/" /><link rel="prev" href="https://acking-you.github.io/posts/tcpconnectionimpl%E5%A6%82%E4%BD%95%E9%AB%98%E6%95%88%E4%B8%94%E7%BB%9F%E4%B8%80%E5%A4%84%E7%90%86io%E4%BA%8B%E4%BB%B6/" /><link rel="next" href="https://acking-you.github.io/posts/lab0-%E5%AE%9E%E7%8E%B0bytestream/" /><link rel="stylesheet" href="/css/page.min.css"><link rel="stylesheet" href="/css/home.min.css"><script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "lab1-实现StreamReassembler",
        "inLanguage": "zh-CN",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "https:\/\/acking-you.github.io\/posts\/lab1-%E5%AE%9E%E7%8E%B0streamreassembler\/"
        },"genre": "posts","keywords": "lab1-实现StreamReassembler","wordcount":  1656 ,
        "url": "https:\/\/acking-you.github.io\/posts\/lab1-%E5%AE%9E%E7%8E%B0streamreassembler\/","datePublished": "2023-04-13T00:00:00+00:00","dateModified": "2023-04-13T00:00:00+00:00","publisher": {
            "@type": "Organization",
            "name": "作者"},"author": {
                "@type": "Person",
                "name": "作者"
            },"description": "lab1-实现StreamReassembler"
    }
    </script></head><body data-header-desktop="auto" data-header-mobile="auto"><script>(window.localStorage && localStorage.getItem('theme') ? localStorage.getItem('theme') === 'dark' : ('auto' === 'auto' ? window.matchMedia('(prefers-color-scheme: dark)').matches : 'auto' === 'dark')) && document.body.setAttribute('theme', 'dark');</script>

        <div id="mask"></div><div class="wrapper"><header class="desktop" id="header-desktop">
    <div class="header-wrapper">
        <div class="header-title">
            <a href="/" title="L_B__">L_B__</a>
        </div>
        <div class="menu">
            <div class="menu-inner"><a class="menu-item" href="/posts/"> 文章 </a><a class="menu-item" href="/tags/"> 标签 </a><a class="menu-item" href="/categories/"> 分类 </a><span class="menu-item delimiter"></span><span class="menu-item search" id="search-desktop">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-desktop">
                        <a href="#" class="search-button search-toggle" id="search-toggle-desktop" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-desktop" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-desktop">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </span><a href="javascript:void(0);" class="menu-item theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div>
        </div>
    </div>
</header><header class="mobile" id="header-mobile">
    <div class="header-container">
        <div class="header-wrapper">
            <div class="header-title">
                <a href="/" title="L_B__">L_B__</a>
            </div>
            <div class="menu-toggle" id="menu-toggle-mobile">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="menu" id="menu-mobile"><div class="search-wrapper">
                    <div class="search mobile" id="search-mobile">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-mobile">
                        <a href="#" class="search-button search-toggle" id="search-toggle-mobile" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-mobile" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-mobile">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </div>
                    <a href="#" class="search-cancel" id="search-cancel-mobile">
                        取消
                    </a>
                </div><a class="menu-item" href="/posts/" title="">文章</a><a class="menu-item" href="/tags/" title="">标签</a><a class="menu-item" href="/categories/" title="">分类</a><div class="menu-item"><a href="javascript:void(0);" class="theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div></div>
    </div>
</header><div class="search-dropdown desktop">
    <div id="search-dropdown-desktop"></div>
</div>
<div class="search-dropdown mobile">
    <div id="search-dropdown-mobile"></div>
</div><main class="main">
                <div class="container"><div class="toc" id="toc-auto">
            <h2 class="toc-title">目录</h2>
            <div class="toc-content" id="toc-content-auto"></div>
        </div><article class="page single" data-toc="disable"><div class="featured-image"><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/img_convert/9c7b214855b7ea22ad8549a1afb50fc7.png#pic_center"
        data-srcset="https://img-blog.csdnimg.cn/img_convert/9c7b214855b7ea22ad8549a1afb50fc7.png#pic_center, https://img-blog.csdnimg.cn/img_convert/9c7b214855b7ea22ad8549a1afb50fc7.png#pic_center 1.5x, https://img-blog.csdnimg.cn/img_convert/9c7b214855b7ea22ad8549a1afb50fc7.png#pic_center 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/img_convert/9c7b214855b7ea22ad8549a1afb50fc7.png#pic_center"
        title="lab1-实现StreamReassembler" /></div><div class="single-card" data-image="true"><h2 class="single-title animated flipInX">lab1-实现StreamReassembler</h2><div class="post-meta">
                <div class="post-meta-line"><span class="post-author"><a href="/" title="Author" rel=" author" class="author"><i class="fas fa-user-circle fa-fw"></i>作者</a></span>&nbsp;<span class="post-category">出版于  <a href="/categories/cs144/"><i class="far fa-folder fa-fw"></i>CS144</a></span></div>
                <div class="post-meta-line"><span><i class="far fa-calendar-alt fa-fw"></i>&nbsp;<time datetime="2023-04-13">2023-04-13</time></span>&nbsp;<span><i class="fas fa-pencil-alt fa-fw"></i>&nbsp;约 1656 字</span>&nbsp;
                    <span><i class="far fa-clock fa-fw"></i>&nbsp;预计阅读 4 分钟</span>&nbsp;</div>
            </div>
            
            <hr><div class="details toc" id="toc-static"  data-kept="">
                    <div class="details-summary toc-title">
                        <span>目录</span>
                        <span><i class="details-icon fas fa-angle-right"></i></span>
                    </div>
                    <div class="details-content toc-content" id="toc-content-static"><nav id="TableOfContents">
  <ul>
    <li><a href="#cs144-lab1">CS144 lab1</a>
      <ul>
        <li><a href="#streamreassembler实现">StreamReassembler实现</a></li>
      </ul>
    </li>
  </ul>
</nav></div>
                </div><div class="content" id="content"><h2 id="cs144-lab1">CS144 lab1</h2>
<p>lab1具体的相关事宜可以查看博客:https://kiprey.github.io/2021/11/cs144-lab1/</p>
<p>完整项目代码: <a href="https://github.com/ACking-you/CS144-Computer-Networks" target="_blank" rel="noopener noreffer">CS144</a></p>
<h3 id="streamreassembler实现">StreamReassembler实现</h3>
<p><code>StreamReassembler</code> 类需要完成对底层发送来的数据的顺序进行正确的重组,如下图:</p>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/1ba0899553ca4a688c0b5da9ff7160a8.png"
        data-srcset="https://img-blog.csdnimg.cn/1ba0899553ca4a688c0b5da9ff7160a8.png, https://img-blog.csdnimg.cn/1ba0899553ca4a688c0b5da9ff7160a8.png 1.5x, https://img-blog.csdnimg.cn/1ba0899553ca4a688c0b5da9ff7160a8.png 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/1ba0899553ca4a688c0b5da9ff7160a8.png"
        title="img" /></p>
<p>具体来说你只需要实现下列的方法:</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">StreamReassembler</span>
<span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
   <span class="c1">// Your code here -- add private members as necessary.
</span><span class="c1"></span>   <span class="n">size_t</span> <span class="n">_unass_base</span><span class="p">;</span>   <span class="c1">//!&lt; The index of the first unassembled byte
</span><span class="c1"></span>   <span class="n">size_t</span> <span class="n">_unass_size</span><span class="p">;</span>   <span class="c1">//!&lt; The number of bytes in the substrings stored but
</span><span class="c1"></span>                         <span class="c1">//!&lt; not yet reassembled
</span><span class="c1"></span>   <span class="kt">bool</span>   <span class="n">_eof</span><span class="p">;</span>          <span class="c1">//!&lt; The last byte has arrived
</span><span class="c1"></span>   <span class="n">std</span><span class="o">::</span><span class="n">string</span>       <span class="n">_buffer</span><span class="p">;</span>   <span class="c1">//!&lt; The unassembled strings
</span><span class="c1"></span>   <span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">bool</span><span class="o">&gt;</span> <span class="n">_bitmap</span><span class="p">;</span>   <span class="c1">//!&lt; buffer bitmap
</span><span class="c1"></span>
   <span class="n">ByteStream</span> <span class="n">_output</span><span class="p">;</span>          <span class="c1">//!&lt; The reassembled in-order byte stream
</span><span class="c1"></span>   <span class="n">size_t</span>     <span class="n">_capacity</span><span class="p">;</span>        <span class="c1">//!&lt; The maximum number of bytes
</span><span class="c1"></span>
<span class="k">public</span><span class="o">:</span>

   <span class="k">explicit</span> <span class="n">StreamReassembler</span><span class="p">(</span><span class="n">size_t</span> <span class="n">capacity</span><span class="p">);</span>

   <span class="kt">void</span> <span class="nf">push_substring</span><span class="p">(</span><span class="k">const</span> <span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="o">&amp;</span><span class="n">data</span><span class="p">,</span> <span class="kt">uint64_t</span> <span class="n">index</span><span class="p">,</span> <span class="kt">bool</span> <span class="n">eof</span><span class="p">);</span>

   <span class="na">[[nodiscard]]</span> <span class="k">const</span> <span class="n">ByteStream</span> <span class="o">&amp;</span><span class="n">stream_out</span><span class="p">()</span> <span class="k">const</span> <span class="p">{</span> <span class="k">return</span> <span class="n">_output</span><span class="p">;</span> <span class="p">}</span>
   <span class="n">ByteStream</span>                     <span class="o">&amp;</span><span class="n">stream_out</span><span class="p">()</span> <span class="p">{</span> <span class="k">return</span> <span class="n">_output</span><span class="p">;</span> <span class="p">}</span>

   <span class="n">size_t</span> <span class="nf">unassembled_bytes</span><span class="p">()</span> <span class="k">const</span><span class="p">;</span>

   <span class="kt">bool</span> <span class="nf">empty</span><span class="p">()</span> <span class="k">const</span><span class="p">;</span>

   <span class="n">size_t</span> <span class="nf">ack_index</span><span class="p">()</span> <span class="k">const</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></div><p>方法有很多,具体最重要的方法是 <code>push_substring(const string&amp; data,uint64_t index,bool eof)</code> ,该方法传入需要重排的数据,以及这个数据开始位置的绝对序号(index),还有表示是否是最后一块数据(eof).</p>
<p>我这里实现重排的逻辑如下:</p>
<p>首先需要一个 <code>bitmap</code> 记录每个序号的数据是否已经存入需要被重排的相应位置中,这个结构记录的数据作用有二:</p>
<ol>
<li>对应序号的数据是否被加入重排队列.</li>
<li>已经重排的数据的下一个序号是否存在连续可重排数据.</li>
</ol>
<p>第一个作用大家都能理解,那么第二个作用是什么意思呢?</p>
<p>每次把数据push进去之后,需要判断是否存在一个连续的需要重排的数据,且这个连续数据的第一个位置是已经重排数据的下一个位置,如果存在,那么需要写入已重排的缓冲区中.</p>
<p>整个数据重排的过程可以用下图进行表示:</p>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/2e19f427c418403384b55ae1911040b8.png"
        data-srcset="https://img-blog.csdnimg.cn/2e19f427c418403384b55ae1911040b8.png, https://img-blog.csdnimg.cn/2e19f427c418403384b55ae1911040b8.png 1.5x, https://img-blog.csdnimg.cn/2e19f427c418403384b55ae1911040b8.png 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/2e19f427c418403384b55ae1911040b8.png"
        title="img" /></p>
<h4 id="具体实现">具体实现</h4>
<p>我们先设计如下成员变量:</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp">   <span class="n">size_t</span> <span class="n">_unass_base</span><span class="p">;</span>   <span class="c1">//!&lt; The index of the first unassembled byte
</span><span class="c1"></span>   <span class="n">size_t</span> <span class="n">_unass_size</span><span class="p">;</span>   <span class="c1">//!&lt; The number of bytes in the substrings stored but
</span><span class="c1"></span>                         <span class="c1">//!&lt; not yet reassembled
</span><span class="c1"></span>   <span class="kt">bool</span>   <span class="n">_eof</span><span class="p">;</span>          <span class="c1">//!&lt; The last byte has arrived
</span><span class="c1"></span>   <span class="n">std</span><span class="o">::</span><span class="n">string</span>       <span class="n">_buffer</span><span class="p">;</span>   <span class="c1">//!&lt; The unassembled strings
</span><span class="c1"></span>   <span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">bool</span><span class="o">&gt;</span> <span class="n">_bitmap</span><span class="p">;</span>   <span class="c1">//!&lt; buffer bitmap
</span><span class="c1"></span>
   <span class="n">ByteStream</span> <span class="n">_output</span><span class="p">;</span>          <span class="c1">//!&lt; The reassembled in-order byte stream
</span><span class="c1"></span>   <span class="n">size_t</span>     <span class="n">_capacity</span><span class="p">;</span>        <span class="c1">//!&lt; The maximum number of bytes
</span></code></pre></div><ul>
<li><code>_unass_base</code> 变量用于表示当前已经重排过多少数据,该值可以结合用户传入的 <code>index</code> 算出用户的数据在待重排队列中的 <code>offset</code> .</li>
<li><code>_unass_size</code> 变量表示待重排数据的长度.</li>
<li><code>_eof</code> 表示传入的数据块是最后一个.</li>
<li><code>_buffer</code> 是待重排的队列.</li>
<li><code>_output</code> 是已重排的队列.</li>
<li><code>_capacity</code> 待重排和已重拍队列的最大容量,且待重排和已重拍(未读取)的数据不能超过这个数值.</li>
</ul>
<p>对于每个数据的重排,分为下列三种情况:</p>
<ol>
<li><code>index-_unass_base&gt;capacity</code> 数据的标号顺序已经超过了当前重排器的最大范围.这个情况直接跳过暂时不进行重排.</li>
<li>在满足不超过capacity的情况下, <code>index &gt;= _unass_base</code> ,需要计算 offset 然后插入待重排队列.</li>
<li>在满足不超过capacity的情况下,<code>index + len &gt; _unass_base</code> ,同样计算offset插入队列,但这个offset的计算过程以及插入的位置均与第二种情况不同.</li>
</ol>
<p>画图表示如下:</p>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="C:%5cUsers%5cAlone%5cAppData%5cRoaming%5cTypora%5ctypora-user-images%5cimage-20230414003300518.png"
        data-srcset="C:%5cUsers%5cAlone%5cAppData%5cRoaming%5cTypora%5ctypora-user-images%5cimage-20230414003300518.png, C:%5cUsers%5cAlone%5cAppData%5cRoaming%5cTypora%5ctypora-user-images%5cimage-20230414003300518.png 1.5x, C:%5cUsers%5cAlone%5cAppData%5cRoaming%5cTypora%5ctypora-user-images%5cimage-20230414003300518.png 2x"
        data-sizes="auto"
        alt="C:\Users\Alone\AppData\Roaming\Typora\typora-user-images\image-20230414003300518.png"
        title="image-20230414003300518" /></p>
<p>在执行完插入待重排队列的操作后,我们还需要检查是重排队列的队头是否存在待重排数据,如果存在,则把整个连续的部分都插入到已重排的队列中,当然整个插入的过程就好像溪水流入的过程一样,需要将这些连续的数据删除,并让后续的数据流到前面来,最后不够capacity的部分补0即可.</p>
<p>讲完整个实现逻辑,我们发现这两个队列非常适合用C++的 <code>std::deque</code> 容器来实现,它既可以按下标访问,又能够支持队列的所有操作.</p>
<p>但是我这里的实现并没有使用 deque 而是普通的 vector 和 string,我建议可以使用deque,网络上的几乎所有实现也都是用的deque.</p>
<p>实现源码如下:</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//! \details This functions calls just after pushing a substring into the
</span><span class="c1">//! _output stream. It aims to check if there exists any contiguous substrings
</span><span class="c1">//! recorded earlier can be push into the stream.
</span><span class="c1"></span><span class="kt">void</span> <span class="n">StreamReassembler</span><span class="o">::</span><span class="n">check_contiguous</span><span class="p">()</span>
<span class="p">{</span>
   <span class="n">size_t</span> <span class="n">len</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
   <span class="k">if</span> <span class="p">(</span><span class="n">_bitmap</span><span class="p">.</span><span class="n">front</span><span class="p">())</span>
   <span class="p">{</span>
      <span class="k">while</span> <span class="p">(</span><span class="n">len</span> <span class="o">&lt;</span> <span class="n">_capacity</span> <span class="o">&amp;&amp;</span> <span class="n">_bitmap</span><span class="p">[</span><span class="n">len</span><span class="p">])</span> <span class="o">++</span><span class="n">len</span><span class="p">;</span>
   <span class="p">}</span>

   <span class="k">if</span> <span class="p">(</span><span class="n">len</span> <span class="o">&gt;</span> <span class="mi">0</span><span class="p">)</span>
   <span class="p">{</span>
      <span class="n">_unass_base</span> <span class="o">+=</span> <span class="n">len</span><span class="p">;</span>
      <span class="n">_unass_size</span> <span class="o">-=</span> <span class="n">len</span><span class="p">;</span>
      <span class="n">_output</span><span class="p">.</span><span class="n">write</span><span class="p">(</span><span class="n">_buffer</span><span class="p">.</span><span class="n">substr</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="n">len</span><span class="p">));</span>
      <span class="c1">// 把流往前推进
</span><span class="c1"></span>      <span class="k">for</span> <span class="p">(</span><span class="n">size_t</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">_capacity</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
      <span class="p">{</span>
         <span class="k">if</span> <span class="p">(</span><span class="n">i</span> <span class="o">+</span> <span class="n">len</span> <span class="o">&lt;</span> <span class="n">_capacity</span><span class="p">)</span>
         <span class="p">{</span>
            <span class="n">_bitmap</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">_bitmap</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="n">len</span><span class="p">];</span>
            <span class="n">_buffer</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">_buffer</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="n">len</span><span class="p">];</span>
         <span class="p">}</span>
         <span class="k">else</span> <span class="p">{</span> <span class="n">_bitmap</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span>
      <span class="p">}</span>
   <span class="p">}</span>
<span class="p">}</span>

<span class="c1">//! \details This function accepts a substring (aka a segment) of bytes,
</span><span class="c1">//! possibly out-of-order, from the logical stream, and assembles any newly
</span><span class="c1">//! contiguous substrings and writes them into the output stream in order.
</span><span class="c1"></span><span class="kt">void</span> <span class="n">StreamReassembler</span><span class="o">::</span><span class="n">push_substring</span><span class="p">(</span><span class="k">const</span> <span class="n">string</span> <span class="o">&amp;</span><span class="n">data</span><span class="p">,</span> <span class="k">const</span> <span class="n">size_t</span> <span class="n">index</span><span class="p">,</span>
                                       <span class="k">const</span> <span class="kt">bool</span> <span class="n">eof</span><span class="p">)</span>
<span class="p">{</span>
   <span class="k">if</span> <span class="p">(</span><span class="n">eof</span><span class="p">)</span> <span class="p">{</span> <span class="n">_eof</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span> <span class="p">}</span>
   <span class="n">size_t</span> <span class="n">len</span> <span class="o">=</span> <span class="n">data</span><span class="p">.</span><span class="n">length</span><span class="p">();</span>
   <span class="k">if</span> <span class="p">(</span><span class="n">len</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">_eof</span> <span class="o">&amp;&amp;</span> <span class="n">_unass_size</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
   <span class="p">{</span>
      <span class="n">_output</span><span class="p">.</span><span class="n">end_input</span><span class="p">();</span>
      <span class="k">return</span><span class="p">;</span>
   <span class="p">}</span>
   <span class="c1">// ignore invalid index
</span><span class="c1"></span>   <span class="k">if</span> <span class="p">(</span><span class="n">index</span> <span class="o">&gt;=</span> <span class="n">_unass_base</span> <span class="o">+</span> <span class="n">_capacity</span><span class="p">)</span> <span class="k">return</span><span class="p">;</span>
   <span class="c1">// 未重排数据的序号大于等于已经重排数据的下一个序号
</span><span class="c1"></span>   <span class="k">if</span> <span class="p">(</span><span class="n">index</span> <span class="o">&gt;=</span> <span class="n">_unass_base</span><span class="p">)</span>
   <span class="p">{</span>
      <span class="kt">int</span>    <span class="n">offset</span>   <span class="o">=</span> <span class="n">index</span> <span class="o">-</span> <span class="n">_unass_base</span><span class="p">;</span>
      <span class="c1">// 减去_output.buffer_size()是为了确保滑动窗口的大小(如果已经重排好的数据没有被读取,那么不一直接收更多的未重排数据)
</span><span class="c1"></span>      <span class="n">size_t</span> <span class="n">real_len</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">len</span><span class="p">,</span> <span class="n">_capacity</span> <span class="o">-</span> <span class="n">_output</span><span class="p">.</span><span class="n">buffer_size</span><span class="p">()</span> <span class="o">-</span> <span class="n">offset</span><span class="p">);</span>
      <span class="k">if</span> <span class="p">(</span><span class="n">real_len</span> <span class="o">&lt;</span> <span class="n">len</span><span class="p">)</span> <span class="p">{</span> <span class="n">_eof</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span>
      <span class="k">for</span> <span class="p">(</span><span class="n">size_t</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">real_len</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
      <span class="p">{</span>
         <span class="k">if</span> <span class="p">(</span><span class="n">_bitmap</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="n">offset</span><span class="p">])</span> <span class="k">continue</span><span class="p">;</span>
         <span class="n">_buffer</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="n">offset</span><span class="p">]</span> <span class="o">=</span> <span class="n">data</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
         <span class="n">_bitmap</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="n">offset</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span>
         <span class="n">_unass_size</span><span class="o">++</span><span class="p">;</span>
      <span class="p">}</span>
   <span class="p">}</span>
   <span class="c1">// 如果未重排数据的序号包含了已经重排的情况,但是整体数据有部分数据未被重排
</span><span class="c1"></span>   <span class="k">else</span> <span class="nf">if</span> <span class="p">(</span><span class="n">index</span> <span class="o">+</span> <span class="n">len</span> <span class="o">&gt;</span> <span class="n">_unass_base</span><span class="p">)</span>
   <span class="p">{</span>
      <span class="kt">int</span>    <span class="n">offset</span>   <span class="o">=</span> <span class="n">_unass_base</span> <span class="o">-</span> <span class="n">index</span><span class="p">;</span>
      <span class="n">size_t</span> <span class="n">real_len</span> <span class="o">=</span> <span class="n">min</span><span class="p">(</span><span class="n">len</span> <span class="o">-</span> <span class="n">offset</span><span class="p">,</span> <span class="n">_capacity</span> <span class="o">-</span> <span class="n">_output</span><span class="p">.</span><span class="n">buffer_size</span><span class="p">());</span>
      <span class="k">if</span> <span class="p">(</span><span class="n">real_len</span> <span class="o">&lt;</span> <span class="n">len</span> <span class="o">-</span> <span class="n">offset</span><span class="p">)</span> <span class="p">{</span> <span class="n">_eof</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span> <span class="p">}</span>
      <span class="k">for</span> <span class="p">(</span><span class="n">size_t</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">real_len</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
      <span class="p">{</span>
         <span class="k">if</span> <span class="p">(</span><span class="n">_bitmap</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="k">continue</span><span class="p">;</span>
         <span class="n">_buffer</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">data</span><span class="p">[</span><span class="n">i</span> <span class="o">+</span> <span class="n">offset</span><span class="p">];</span>
         <span class="n">_bitmap</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span>
         <span class="n">_unass_size</span><span class="o">++</span><span class="p">;</span>
      <span class="p">}</span>
   <span class="p">}</span>
   <span class="n">check_contiguous</span><span class="p">();</span>
   <span class="k">if</span> <span class="p">(</span><span class="n">_eof</span> <span class="o">&amp;&amp;</span> <span class="n">_unass_size</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="p">{</span> <span class="n">_output</span><span class="p">.</span><span class="n">end_input</span><span class="p">();</span> <span class="p">}</span>
<span class="p">}</span>
</code></pre></div></div><div class="post-footer" id="post-footer">
    <div class="post-info"><div class="post-info-tag"><span><a href="/tags/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/">lab1-实现StreamReassembler</a>
                </span></div><div class="post-info-line"><div class="post-info-mod">
                <span>更新于 2023-04-13</span>
            </div><div class="post-info-mod"></div>
        </div><div class="post-info-share">
            <span><a href="javascript:void(0);" title="分享到 Twitter" data-sharer="twitter" data-url="https://acking-you.github.io/posts/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/" data-title="lab1-实现StreamReassembler" data-hashtags="lab1-实现StreamReassembler"><i class="fab fa-twitter fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Facebook" data-sharer="facebook" data-url="https://acking-you.github.io/posts/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/" data-hashtag="lab1-实现StreamReassembler"><i class="fab fa-facebook-square fa-fw"></i></a><a href="javascript:void(0);" title="分享到 WhatsApp" data-sharer="whatsapp" data-url="https://acking-you.github.io/posts/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/" data-title="lab1-实现StreamReassembler" data-web><i class="fab fa-whatsapp fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Line" data-sharer="line" data-url="https://acking-you.github.io/posts/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/" data-title="lab1-实现StreamReassembler"><i class="fab fa-line fa-fw"></i></a><a href="javascript:void(0);" title="分享到 微博" data-sharer="weibo" data-url="https://acking-you.github.io/posts/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/" data-title="lab1-实现StreamReassembler" data-image="https://img-blog.csdnimg.cn/img_convert/9c7b214855b7ea22ad8549a1afb50fc7.png#pic_center"><i class="fab fa-weibo fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Myspace" data-sharer="myspace" data-url="https://acking-you.github.io/posts/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/" data-title="lab1-实现StreamReassembler" data-description="lab1-实现StreamReassembler"><i data-svg-src="/lib/simple-icons/icons/myspace.min.svg"></i></a><a href="javascript:void(0);" title="分享到 Blogger" data-sharer="blogger" data-url="https://acking-you.github.io/posts/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/" data-title="lab1-实现StreamReassembler" data-description="lab1-实现StreamReassembler"><i class="fab fa-blogger fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Evernote" data-sharer="evernote" data-url="https://acking-you.github.io/posts/lab1-%E5%AE%9E%E7%8E%B0streamreassembler/" data-title="lab1-实现StreamReassembler"><i class="fab fa-evernote fa-fw"></i></a></span>
        </div></div><div class="post-nav"><a href="/posts/tcpconnectionimpl%E5%A6%82%E4%BD%95%E9%AB%98%E6%95%88%E4%B8%94%E7%BB%9F%E4%B8%80%E5%A4%84%E7%90%86io%E4%BA%8B%E4%BB%B6/" class="prev" rel="prev" title="TcpConnectionImpl如何高效且统一处理IO事件"><i class="fas fa-angle-left fa-fw"></i>Previous Post</a>
            <a href="/posts/lab0-%E5%AE%9E%E7%8E%B0bytestream/" class="next" rel="next" title="lab0-实现ByteStream">Next Post<i class="fas fa-angle-right fa-fw"></i></a></div></div>
</div></article></div>
            </main>
            <footer class="footer"><div class="footer-container"><div class="footer-line">由 <a href="https://gohugo.io/" target="_blank" rel="noopener noreffer" title="Hugo 0.86.0">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/khusika/FeelIt" target="_blank" rel="noopener noreffer" title="FeelIt 1.0.1"><i class="fas fa-hand-holding-heart fa-fw"></i> FeelIt</a>
        </div><div class="footer-line" itemscope itemtype="http://schema.org/CreativeWork"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2023</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="/"></a></span></div>
</div>
</footer>
        </div>

        <div id="fixed-buttons"><a href="#" id="back-to-top" class="fixed-button" title="回到顶部">
                <i class="fas fa-chevron-up fa-fw"></i>
            </a></div><link rel="stylesheet" href="/lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="/lib/animate/animate.min.css"><link rel="stylesheet" href="/lib/katex/katex.min.css"><link rel="stylesheet" href="/lib/katex/copy-tex.min.css"><script src="/lib/autocomplete/autocomplete.min.js"></script><script src="/lib/lunr/lunr.min.js"></script><script src="/lib/lunr/lunr.stemmer.support.min.js"></script><script src="/lib/lunr/lunr.zh.min.js"></script><script src="/lib/lazysizes/lazysizes.min.js"></script><script src="/lib/clipboard/clipboard.min.js"></script><script src="/lib/sharer/sharer.min.js"></script><script src="/lib/katex/katex.min.js"></script><script src="/lib/katex/auto-render.min.js"></script><script src="/lib/katex/copy-tex.min.js"></script><script src="/lib/katex/mhchem.min.js"></script><script>window.config={"code":{"copyTitle":"复制到剪贴板","maxShownLines":200},"comment":{},"math":{"delimiters":[{"display":true,"left":"$$","right":"$$"},{"display":true,"left":"\\[","right":"\\]"},{"display":false,"left":"$","right":"$"},{"display":false,"left":"\\(","right":"\\)"}],"strict":false},"search":{"highlightTag":"em","lunrIndexURL":"/index.json","lunrLanguageCode":"zh","lunrSegmentitURL":"/lib/lunr/lunr.segmentit.js","maxResultLength":100,"noResultsFound":"没有找到结果","snippetLength":50,"type":"lunr"}};</script><script src="/js/theme.min.js"></script></body></html>
